package NC36_在两个长度相等的排序数组中找到上中位数;
import java.util.*;


public class Solution {
    /**
     * find median in two sorted array
     * @param arr1 int整型一维数组 the array1
     * @param arr2 int整型一维数组 the array2
     * @return int整型
     */
    public int findMedianinTwoSortedAray (int[] arr1, int[] arr2) {
        // write code here
        int len1 = arr1.length;
        int len2 = arr2.length;
        int mid_index = (len1 + len2) / 2;
        int index = 0;  // 走过的次数
        int res = arr1[0];  // 存放最新走过的值
        int index1 = 0, index2 = 0;
        while (index1 < len1 && index2 < len2){
            // 小的放入 res 中
            if (arr1[index1] < arr2[index2]){
                res = arr1[index1];
                index1++;
            }else {
                res = arr2[index2];
                index2++;
            }
            // 当总的次数 index 等于 mid_index,证明 res 为上中位数
            if (index == mid_index - 1){
                return res;
            }
            index++;
        }
        // arr2 走完，中位数在 arr1 中
        if (index != mid_index && index1 < len1){
            return arr1[index1 + mid_index - 1 - index];
        }else {
            return arr2[index2 + mid_index - 1 - index];
        }
    }
}